package com.chenchao.javaarray;

import java.util.Arrays;

/**
 * @encoding : UTF-8
 * @Time : 2020/11/7 19:40
 * @Author : Chen Chao
 * @File : javaSE.com.chenchao.javaarray.BubbleSort.java
 * @Software : IntelliJ IDEA
 * @since : 1.8
 */
public class Sort {
    public static void main(String[] args) {
        //int[] b={1,2,3,4,5};
        int[] a={3,2,7,4,9};
        int[] c = {5, 4, 3, 2, 1,0,-1,-2};

        //System.out.println(Arrays.toString(sort(a)));
        //System.out.println(Arrays.toString(sort(b)));
        //System.out.println(Arrays.toString(bubbleSort(c)));
        System.out.println(Arrays.toString(selectSort(a)));
        System.out.println(binarySearch(selectSort(a), 6));
        int[][] b2=new int[][]{a,c};
        //二维数组的子数组长度可以不同
        for (int[] ints : b2) {
            System.out.println(Arrays.toString(ints));
        }

    }

    /**
     * sort 冒泡排序，核心思想每一轮产生一个最大或者最小的数，减少下一轮排序次数
     *
     * @param array 要冒泡排序的数组
     * @return
     */
    public static int[] bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            //最后一次只剩一个也是不用排序的
            boolean flag = true;//优化算法，如果已经拍好直接跳出
            for (int j = 0; j < array.length - i - 1; j++) {
                //注意超出边界问题
                if (array[j] < array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    flag = false;
                }
            }
            if (flag) {
                System.out.println("已排好的数组");
                break;
            }
        }
        return array;
    }

    /**
     * selectSort 选择排序
     * @param array 要排序的数组
     * @return array 返回拍好的数组
     */
    public static int[] selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;
            for (int j = i; j < array.length; j++) {
                if (array[j]<array[i])
                    minIndex=j;
            }
            int temp=array[minIndex];
            array[minIndex]=array[i];
            array[i]= temp;//找出最小角标进行交换
        }
        return array;
    }

    /**
     * binarySearch二分查找
     * @param array 要查找的数组
     * @param value 要查找的值
     * @return 如果返回-1则不在数组中
     */
    public static int binarySearch(int[] array ,int value){
        int lowIndex=0;
        int highIndex=array.length-1;
        if(value>array[highIndex]|value<array[lowIndex])
            return -1;
        while (lowIndex<=highIndex){
            int midIndex=(lowIndex+highIndex)>>>1;
            if(array[midIndex]==value)
                return midIndex;
            else if(array[midIndex]>value)
                highIndex=midIndex-1;
            else if(array[midIndex]<value)
                lowIndex=midIndex+1;
        }
        return -1;
    }

}
